package class_0917skiplistextends;

import java.util.*;

/*跳跃表 */
public class SkipList<K extends Comparable<K>,V> implements Iterable<SkipList.Node<K,V>>{

    private static final int MAX_LEVEL = 16;//跳表允许的最大层数
    private static final double PROBABILITY = 0.5; // 定义概率常量
    private final Node<K,V> dummyHead = new Node<K,V>(null, null, MAX_LEVEL);
    private final Node<K,V> dummyTail = new Node<K,V>(null, null, 0);

    {
        for (int i = 0; i < MAX_LEVEL; i++) {
            dummyHead.forwards[i] = dummyTail;
        }
    }

    private int randomLevel() {
        int level = 1;//基础层，每个等级节点都应该保证其至少有一层存储原始链表
        while (Math.random() < PROBABILITY && level < MAX_LEVEL) {
            //随机的生成更高层数
            level++;
        }
        return level;//返回
    }
    private Comparator<K> comparator;
    private int curLevel;//跳表层数
    private int size;//链表长度

    public SkipList() {
        curLevel = 1;
        size = 0;
    }

    public SkipList(Comparator<K> comparator) {
        this();
        this.comparator = comparator;
    }
    //提供修改迭代器的两个接口
    public void setComparator(Comparator<K> comparator) {
        this.comparator = comparator;
    }
    public void clearComparator(){
        this.comparator = null;
    }
    //等级节点的定义。
    public static class Node<K extends Comparable<K>, V> {
        K key; //键
        V value; //值
        Node<K,V>[] forwards; //前向指针数组

        public Node(K key, V value, int level) {
            this.key = key;
            this.value = value;
            this.forwards = (Node<K,V>[]) new Node[level];//前向指针有多少个，或者该等级节点
        }
        @Override
        public boolean equals(Object obj) {
            return this.key.equals(((Node<K,V>)obj).key)
                    && this.value.equals(((Node<K,V>)obj).value);
        }
        @Override
        public String toString() {
            return "[" +
                    key +
                    " -> " +
                    value +
                    "]";
        }
        public K getKey(){
            return key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public Node<K,V>[] getForwards() {
            return forwards;
        }
    }
    private Node<K,V> searchOneLevel(K key) {
        return comparator==null?searchOneLevelComparable(key)
                :searchOneLevelComparator(key);
    }
    private Node<K,V> searchOneLevelComparable(K key) {
        Node<K,V> cur = dummyHead; // 从头节点开始遍历
        // 从最高层开始逐层向下遍历---尽可能靠近，越近越好。
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.forwards[i] != dummyTail && cur.forwards[i].key.compareTo(key)<0) {
                cur = cur.forwards[i]; // 在当前层前进---尽可能往右走
            }
        }
        return cur;
    }

    private Node<K,V> searchOneLevelComparator(K key) {
        Node<K, V> cur = dummyHead;
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.forwards[i] != dummyTail && comparator.compare(cur.forwards[i].key, key) < 0) {
                cur = cur.forwards[i];
            }
        }
        return cur;
    }
    private Node<K,V> searchUpdate(K key,Node<K,V>[] update){
        return comparator==null?searchUpdateComparable(key,update)
                : searchUpdateComparator(key,update);
    }
    private Node<K,V> searchUpdateComparator(K key,Node<K,V>[] update){
        Node<K,V> cur = dummyHead;
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.forwards[i] != dummyTail && comparator.compare(cur.forwards[i].key, key) < 0) {
                cur = cur.forwards[i];
            }
            update[i] = cur;
        }
        return cur;
    }
    private Node<K,V> searchUpdateComparable(K key,Node<K,V>[] update){
        Node<K,V> cur = dummyHead;
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.forwards[i] != dummyTail && cur.forwards[i].key.compareTo(key) < 0) {
                cur = cur.forwards[i];
            }
            update[i] = cur;
        }
        return cur;
    }
    public Node<K,V> search(K key) {
        Node<K,V> cur;
        cur = comparator != null? searchOneLevelComparator(key): searchOneLevel(key);
        // 回到第0层（原始层），找到目标节点
        cur = cur.forwards[0];

        // 如果目标节点存在且与目标key匹配，则返回该节点
        if (cur != dummyTail && cur.key.compareTo(key)==0) {
            return cur;
        } else {
            // 如果结果是哨兵节点dummyTail，或者cur.key != key，键为key的节点不存在。
            return null;
        }
    }

    public void insert(K key, V value) {
        Node<K,V>[] update = (Node<K,V>[])new Node[curLevel];
        Node<K,V> cur = searchUpdate(key,update);
        //cur是第一层key关键字节点理论位置的的前驱节点
        //现在往后讨论
        cur = cur.forwards[0];
        if (cur != dummyTail) {
            if((comparator != null && comparator.compare(cur.key,key)==0)
            ||cur.key.compareTo(key)==0) {
                cur.value = value;
                return ;
            }
        }
        // 如果key不存在，进行插入操作
        // 生成新节点的随机层数
        int level = randomLevel();
        //创建新节点
        Node<K,V> newNode = new Node<>(key, value, level);

        // 插入新节点，更新每层的前驱指针
        // 插入新节点，更新前向指针
        for (int i = 0; i < level; i++) {
            if (i < curLevel) {
                newNode.forwards[i] = update[i].forwards[i];
                update[i].forwards[i] = newNode;
            } else {
                // 新增的层级部分
                dummyHead.forwards[i] = newNode;
                newNode.forwards[i] = dummyTail;
            }
        }
        if(level>curLevel) {
            curLevel = level;
        }
        this.size++;
    }

    public void delete(K key) {
        Node<K,V>[] update = (Node<K,V>[]) new Node[curLevel];
        Node<K,V> cur = searchUpdate(key,update);
        cur = cur.forwards[0];
        if(cur == dummyTail) {
            return;
        }
        if(comparator!=null ){
            if(comparator.compare(cur.key,key)==0){
                for (int i = 0; i < cur.forwards.length; i++) {
                    update[i].forwards[i] = cur.forwards[i];
                }
            }
        }
        else{
            if(cur.key.compareTo(key)==0){
                for (int i = 0; i < cur.forwards.length; i++) {
                    update[i].forwards[i] = cur.forwards[i];
                }
            }
        }
        while(curLevel>1 && dummyHead.forwards[curLevel-1]==dummyTail){
            curLevel--;
        }
        this.size--;
    }

    public void delete(Node<K,V> node){
        delete(node.key);
    }
    public boolean isEmpty(){
        return size==0;
    }
    public int size(){
        return size;
    }
    public int level(){
        return curLevel;
    }
    public void put(K key, V value) {
        insert(key,value);
    }

    public void clear(){
        size = 0;
        curLevel = 1;
        for (int i = 0; i < curLevel; i++) {
            dummyHead.forwards[i] = dummyTail;
        }
    }

    public Node<K,V> getPrevNode(Node<K,V> node){
        return search(node.key);
    }
    public Node<K,V> getNextNode(Node<K,V> node){
        return node.forwards[0]==null?null:node.forwards[0];
    }


    //跳表扩展操作
    /*获取指定闭区间的节点 */
    public List<V> rangeSearch(K lowKey, K highKey) {
        List<V> list = new ArrayList<>();
        Node<K,V> low = search(lowKey);
        low = low.forwards[0];
        //比较器优先
        while(low!=dummyTail
                &&(comparator!=null?comparator.compare(low.key,highKey) < 0
                :low.key.compareTo(highKey) < 0)){
            list.add(low.value);
            low = low.forwards[0];
        }
        return list;
    }
    /*删除指定闭区间的节点*/
    public void rangeDelete(K lowKey, K highKey) {
        Node<K,V> low = search(lowKey);
        low = low.forwards[0];
        while(low!=dummyTail
                &&(comparator!=null?comparator.compare(low.key,highKey) < 0
                :low.key.compareTo(highKey) < 0)){
            delete(low.key);
            low = low.forwards[0];
        }
    }
    /*支持批量插入 */
    public void bulkInsert(Map<K, V> keyValuePairs) {
        for (Map.Entry<K, V> entry : keyValuePairs.entrySet()) {
            insert(entry.getKey(), entry.getValue());
        }
    }

    /*合并跳表 */
    public void merge(SkipList<K,V> other) {
        Node<K,V> cur = other.dummyHead.forwards[0];

        // 遍历另一个跳表的所有节点
        while (cur != other.dummyTail) {
            insert(cur.key, cur.value);  // 将所有节点插入到当前跳表
            cur = cur.forwards[0];
        }
    }

    /*重新排列跳表 */
    public void reBalance(){
        List<Node<K,V>> list = new ArrayList<>();
        Node<K,V> cur = dummyHead;
        while(cur.forwards[0]!=dummyTail){
            list.add(cur.forwards[0]);
            cur = cur.forwards[0];
        }

        this.clear();

        for(Node<K,V> node : list) {
            insert(node.key, node.value);
        }
    }


    //---:Object
    public boolean equals(SkipList<K,V> other) {
        if (this == other) {
            return true; // 如果两个引用相同，则直接返回 true
        }

        if (other == null || this.size != other.size()) {
            return false; // 如果另一个 SkipList 为 null 或者大小不同，返回 false
        }

        Node<K, V> node1 = this.dummyHead.forwards[0]; // 获取当前跳表的第一个节点
        Node<K, V> node2 = other.dummyHead.forwards[0]; // 获取另一个跳表的第一个节点

        while (node1 != dummyTail && node2 != other.dummyTail) {
            // 如果某一层的键或值不相等，则跳表不相等
            if (!node1.key.equals(node2.key) || !node1.value.equals(node2.value)) {
                return false;
            }
            // 继续遍历下一层
            node1 = node1.forwards[0];
            node2 = node2.forwards[0];
        }

        // 如果都遍历到 dummyTail，说明跳表相等
        return node1 == dummyTail && node2 == other.dummyTail;
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(Node<K,V> node:this){
            sb.append(node.toString());
        }
        sb.append("]");
        return sb.toString();
    }
    /*跳跃表的迭代器实现 */
    public Iterator<Node<K,V>> iterator() {
        return new SkipListIterator<Node<K,V>>();
    }

    private class SkipListIterator<T> implements Iterator<T>{
        private Node<K, V> current;
        private int currentLevel; // 记录当前层数


        public SkipListIterator() {
            current = dummyHead.forwards[0];
            currentLevel = 1;
        }

        // 获取当前节点的高度
        public int getCurrentHeight() {
            if (current == dummyTail) {
                return 1; // 头尾节点高度为0
            }
            return current.forwards.length; // 返回当前节点的高度
        }
        //上升到指定高度去找节点， 高度[1, curLevel]
        public void ascendToLevel(int targetLevel) {
            if (targetLevel <= 0 || targetLevel > curLevel) {
                throw new IllegalArgumentException("Invalid level");
            }

            // 从当前层数逐步上升，找到对应的节点
            while (currentLevel < targetLevel) {
                if (current.forwards[currentLevel-1] != null) {
                    current = current.forwards[currentLevel-1]; // 向前移动
                }
                currentLevel++; // 上升一层
            }
        }
        @Override
        public boolean hasNext() {
            return current != dummyTail;
        }

        @Override
        public T next() throws NoSuchElementException {
            if(current == dummyTail){
                throw new NoSuchElementException();
            }
            //存储当前节点， 然后往后移动。
            Node<K,V> tmp = current;
            current = current.forwards[0];
            return (T)tmp;
        }

        @Override
        public void remove() throws NoSuchElementException{
            if(current == dummyTail){
                throw new NoSuchElementException();
            }
            delete(current);
            Iterator.super.remove();
        }

    }
}

